Discrete Logarithm
This note handles the construction of the discrete logarithm from its inverse function.
Let \(G\) be a group with \(g \in G\). Then the function \(f : \mathbb{Z}_{\mathrm{ord}(g)} \to \langle g \rangle\) defined by
is an isomorphism.
This follows easily from the fact that powers up to order in group are distinct.
Given this isomorphism, a natural question to ask is what is the inverse function. In this case, we define the discrete logarithm to be exactly that.
Given an element \(g\) in a group \(G\), we define the discrete logarithm to the base \(g\) to be a function \(\log_g : \langle g \rangle \to \mathbb{Z}_{\mathrm{ord}(g)}\) given by
where \(k \in \mathbb{Z}_{\mathrm{ord}(g)}\) such that
Of course, using a generator (or primitive root) \(g\) we end up with an isomorphism between \(G\) and \(Z_{|G|}\) which is much more natural to work with.
We also often call the discrete logarithm \(\log_g : G \to \mathbb{Z}_n\) the index modulo \(n\) relative to \(g\), and denote it by \(\mathrm{ind}_g\).
In the case of the multiplicative group of integers modulo n, we have the isomorphism: